typedef char STDatetype;
typedef struct Stack
{
	STDatetype* a;
	int capacity;
	int top;                 //初始化为0,表示栈顶位置下一个位置的下标
}ST;
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = (STDatetype*)malloc(sizeof(STDatetype) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	ps->top = 0;
	ps->capacity = 4;
}


void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

void StackPush(ST* ps,STDatetype x)
{
	assert(ps);                  //防止是一个没有初始化的空栈
	if (ps->top == ps->capacity)
	{
		STDatetype* tmp = (STDatetype*)realloc(ps->a, ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
	ps->a[ps->top] = x;                //因为top初始化为0,所以先入栈再++;
	ps->top++;
}


bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

STDatetype StackTop(ST* ps)              //输出栈顶元素
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top-1];
}

bool isValid(char * s){
ST st;
StackInit(&st);
while(*s)
{
    if(*s=='['||*s=='('||*s=='{')
    {
        StackPush(&st,*s);
        ++s;
    }
    else
    {
        if(StackEmpty(&st))
            return false;
        char top =StackTop(&st);
        StackPop(&st);
        //不匹配
        if((*s==']'&&top!='[')||(*s=='}'&&top!='{')||(*s==')'&&top!='('))
        {
        return false;
        }
        //匹配
        else
        {
            s++;
        }
            
    }
}
bool ret=StackEmpty(&st);
StackDestroy(&st);
return ret;
}